#ifndef __INTERSECTIONS__H
#define __INTERSECTIONS__H

#include "Vector3.h"
#include "Utilities.h"

bool triangle_rectangle_intersection(Point p1, Point p2, Point p3, Point r1, Point r2, Point r3, Point r4) {
	Point triangle[3] = {p1, p2, p3};
	Point rectangle[4] = {r1, r2, r3, r4};

	double x1 = p1[0]; double y1=p1[1];
        double x2 = p2[0]; double y2=p2[1];
	double x3 = p3[0]; double y3=p3[1];

	// For each vertex in the rectangle, see if it's inside the triangle.
	for (int i=0; i<4; i++) { // For each point in rectangle,
		// compute the barycentric coordinates of that rectangle.

		double x = rectangle[i][0];
		double y = rectangle[i][1];

		double lambda_one = ((y2-y3)*(x-x3)) + ((x3-x2)*(y-y3));
		lambda_one /= (((y2-y3)*(x1-x3))+((x3-x2)*(y1-y3)));
		
		double lambda_two = ((y3-y1)*(x-x3))+((x1-x3)*(y-y3));
		lambda_two /= ((y2-y3)*(x1-x3)+(x3-x2)*(y1-y3));
		
		double lambda_three = 1.0-lambda_one-lambda_two;

		if (0 <= lambda_one && 0 <= lambda_two && 0 <= lambda_three && lambda_one <= 1 && lambda_two <= 1 && lambda_three <= 1)
			return true; // inside!
	}


	// For each vertex in the triangle, see if it's inside the rectangle.
	Point lower_left(min(r1[0], r2[0], r3[0], r4[0]), 
                         min(r1[1], r2[1], r3[1], r4[1]));

	Point upper_right(max(r1[0], r2[0], r3[0], r4[0]), 
                          max(r1[1], r2[1], r3[1], r4[1]));

	
	for (int i=0; i<3; i++) {
		if (lower_left[0] <= triangle[i][0] && triangle[i][0] <= upper_right[0])
			if (lower_left[1] <= triangle[i][1] && triangle[i][1] <= upper_right[1])
				return true; // I knew it!
	}


	// For each pair of edges, see if they intersect in any way.
	// It doesn't matter if we compute the intersection with the diagonal of the triangle - it is already covered earlier anyway. So no need for extra red tape there.
	for (int ONE=0; ONE<4; ONE++) {
		for (int TWO=0; TWO<4; TWO++) {
			if (ONE==TWO) continue; // life goes on
			
			for (int i=0; i<3; i++) {
				// Line from the rectangle
				double A_1 = rectangle[TWO][1] - rectangle[ONE][1];
				double B_1 = rectangle[ONE][0] - rectangle[TWO][0];
				double C_1 = A_1*rectangle[ONE][0] + B_1*rectangle[ONE][1];
				
				// Line from the triangle
				int TRI_ONE = i;
				int TRI_TWO = (i+1)%3;
				double A_2 = triangle[TRI_TWO][1] - triangle[TRI_ONE][0];
				double B_2 = triangle[TRI_ONE][0] - triangle[TRI_TWO][0];
				double C_2 = A_2*triangle[TRI_ONE][0] + B_2*triangle[TRI_TWO][1];

				double det = A_1*B_2 - A_2*B_1;
				if (det == 0)
					return false;
				else
					{
						double X = (B_2*C_1 - B_1*C_2)/det;
						double Y = (A_1*C_2 - A_2*C_1)/det;
						
						double min_x_r = min(rectangle[ONE][0], rectangle[TWO][0]);
						double min_x_t = min(triangle[TRI_ONE][0], triangle[TRI_TWO][0]);
						double min_x = min(min_x_r, min_x_t);

						double max_x_r = max(rectangle[ONE][0], rectangle[TWO][0]);
						double max_x_t = max(triangle[TRI_ONE][0], triangle[TRI_TWO][0]);
						double max_x = max(max_x_r, max_x_t);


						
						double min_y_r = min(rectangle[ONE][1], rectangle[TWO][1]);
						double min_y_t = min(triangle[TRI_ONE][1], triangle[TRI_TWO][1]);
						double min_y = min(min_y_r, min_y_t);

						double max_y_r = max(rectangle[ONE][1], rectangle[TWO][1]);
						double max_y_t = max(triangle[TRI_ONE][1], triangle[TRI_TWO][1]);
						double max_y = max(max_y_r, max_y_t);
						
						if (min_x <= X && X <= max_x && min_y <= Y && Y <= max_y)
							return true;
					}
			}
		}
	}
	
       
	

	return false; // No intersection at all!
}

#endif
